package com.example.leetcode.graph.common.unionfind.onedimension.quickunion;

public class UnionFind {
    // 存的是父结点，而不是根节点，需要递归向上查找根节点
    int[] root;

    public UnionFind(int size) {
        root = new int[size];
        for (int i = 0; i < size; i++) {
            root[i] = i;
        }
    }

    /**
     * 使用迭代的写法
     *
     * @param x
     * @return
     */
    public int find(int x) {
        // 循环向上查找父元素，直到父元素等于自身即为根元素
        while (x != root[x]) {
            x = root[x];
        }
        return x;
    }

    /**
     * 使用递归的写法
     *
     * @param x
     * @return
     */
    public int find2(int x) {
        if (x == root[x]) {
            return x;
        }
        return find2(root[x]);
    }

    /**
     * rootY 向 rootX 合并
     * 直接两个根节点相连
     *
     * @param x
     * @param y
     */
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            // 更新父结点，将rootY节点挂到rootX下
            root[rootY] = rootX;
        }
    }

    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }
}